home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / program / swagg_m.zip / MATH.SWG / 0084_Pentium-Optimized Permutations.pas < prev    next >
Pascal/Delphi Source File  |  1995-03-03  |  2KB  |  94 lines
  1. {
  2. Just for fun, I sat down last night and generated an inline asm version
  3. of the C code I posted that permuted character strings.  This version
  4. uses about 90 clock cycles/call on a 486 and 60 on a Pentium, i.e.
  5. one microsecond/call on my P5-60:  (The average time is very nearly
  6. independent of the length of the string.)
  7.  
  8. From: terjem@hda.hydro.com (Terje Mathisen)
  9. }
  10.  
  11. {$R-,S-}
  12. Program Permutate;
  13.  
  14. Function Permute(var a; alen : word): Boolean;
  15. Assembler;
  16. asm
  17.   push ds         { BX -> beginning of array }
  18.   lds bx,[a]
  19.   mov di,[alen]   { Array length }
  20.   xor cx,cx       { Return value = False }
  21.   lea si,[di+bx-2]{ SI -> one character before last }
  22.   lea di,[di+bx-1]{ DI -> last position in a[] }
  23.  
  24. @loop1:
  25.   cmp si,bx       { Check if we've gotten to the beginning of the array!}
  26.    jb @reverse    { Yes, so no permutation found, return reversed array!}
  27.   mov ax,[si]     { Get another pair of bytes from the end }
  28.   dec si
  29.   cmp al,ah
  30.    jae @loop1     { Loop until a[si] < a[si+1] }
  31.  
  32. { We have found a pair of bytes where the first is less than
  33.   the second, which means that there exists at least one more
  34.   permutation of the a[] array.
  35. }
  36.  
  37.   mov bx,di       { BX -> Last byte in a[] }
  38.   inc si          { SI was decremented one extra time, adjust back }
  39.   mov cl,True     { Return value = True }
  40.  
  41. { Find the last byte which is > al (a[si]) }
  42.  
  43. @loop2:
  44.   mov dl,[bx]
  45.   dec bx
  46.   cmp dl,al
  47.    jbe @loop2
  48.  
  49. { Swap the two positions found: }
  50.  
  51.   mov [si],dl
  52.   mov [bx+1],al
  53.    jmp @reverse   { Reverse the rest of the array! }
  54.  
  55. @loop3:
  56.   mov al,[si]
  57.   mov dl,[di]
  58.   mov [di],al
  59.   dec di
  60.   mov [si],dl
  61. @reverse:
  62.   inc si
  63.   cmp si,di
  64.    jb @loop3
  65.  
  66.   mov ax,cx
  67.   pop ds
  68. end;
  69.  
  70. var
  71.   test, org : String;
  72.   n : LongInt;
  73.  
  74. begin
  75.   org := ParamStr(1);
  76.   test := org;
  77.   n := 0;
  78.  
  79.   if ParamCount > 1 then begin {Verbose version }
  80.     repeat
  81.       WriteLn(n:10,' ',test);
  82.       Inc(n);
  83.     until not Permute(test[1],Length(test));
  84.     WriteLn(n:10,' ',test);
  85.   end
  86.   else begin
  87.     repeat
  88.       Inc(n);
  89.     until not Permute(test[1],Length(test));
  90.     WriteLn(n,' permutations of ',org,' found!');
  91.   end;
  92. end.
  93.  
  94.